Write a function that takes
a list of characters and reverses the
letters
in place.
↴
An in-place function
modifies data structures or objects outside of its
own
stack frame
↴
The call stack is what a program uses to keep
track of function calls. The call stack is
made up of stack frames—one for
each function call.
For instance, say we called a function that
rolled two dice and printed the sum.
First, our program calls roll_two_and_sum(). It goes
on the call stack:
That function calls roll_die(), which gets pushed
on to the top of the call stack:
Inside of roll_die(), we call random.randint().
Here's what our call stack looks like then:
When random.randint() finishes, we return back to
roll_die() by removing
("popping") random.randint()'s stack frame.
Same thing when roll_die() returns:
We're not done yet! roll_two_and_sum()
calls roll_die() again:
Which calls random.randint() again:
random.randint() returns, then roll_die() returns,
putting us back in roll_two_and_sum():
Which calls print()():
What actually goes in a function's
stack frame?
A stack frame usually stores:
Some of the specifics vary between processor architectures. For
instance, AMD64 (64-bit x86) processors pass some arguments in
registers and some on the call stack. And, ARM processors (common
in phones) store the return address in a special register instead
of putting it on the call stack.
Each function call creates its own stack
frame, taking up space on the call stack. That's important
because it can impact the space complexity of an algorithm.
Especially when we use recursion.
For example, if we wanted to multiply all the numbers
between 1 and n,
we could use this recursive approach:
What would the call stack look like
when n = 10?
First, product_1_to_n() gets called
with n = 10:
This calls product_1_to_n() with
n = 9.
Which calls product_1_to_n()
with n = 8.
And so on until we get to n = 1.
Look at the size of all those stack frames! The entire call stack
takes up O(n) space. That's right—we
have an O(n) space cost even though
our function itself doesn't create any data
structures!
What if we'd used an iterative approach instead of a recursive one?
This version takes a constant amount of space. At the beginning of the loop,
the call stack looks like this:
As we iterate through the loop, the local variables change, but we
stay in the same stack frame because we don't call any other
functions.
In general, even though the compiler or interpreter will take
care of managing the call stack for you, it's important to consider the
depth of the call stack when analyzing the space complexity of an
algorithm.
Be especially careful with recursive functions!
They can end up building huge call stacks.
What happens if we run out of space? It's a stack
overflow! In Python 3.6, you'll get
a RecursionError.
If the very last thing
a function does is call
another function, then its stack frame
might not be needed any more. The function
could free up its stack frame before doing its final
call, saving space.
This is called tail call optimization
(TCO). If a recursive function is optimized with TCO, then it
may not end up with a big call stack.
In general, most languages don't provide TCO. Scheme
is one of the few languages that guarantee tail call
optimization. Some Ruby, C, and Javascript
implementations may do it. Python and Java decidedly
don't.
In-place algorithms are sometimes called
destructive, since the original input is
"destroyed" (or modified) during
the function call.
Careful: "In-place" does not mean "without
creating any additional variables!" Rather, it means
"without creating a new copy of the input." In general, an
in-place function will only create
additional variables that are O(1) space.
An out-of-place function
doesn't make any changes that are visible to
other functions. Usually,
those functions copy any data structures or objects
before manipulating and changing them.
In many languages, primitive values (integers,
floating point numbers, or characters) are copied when passed as
arguments, and more complex data structures
(lists, heaps, or hash tables) are
passed by
reference. This is what Python does.
Here are two functions that do the same
operation on a list, except one is
in-place and the other is out-of-place:
Working in-place is a good way to save time and
space. An in-place algorithm avoids the cost of
initializing or copying data structures, and it usually has
an O(1) space cost.
But be careful: an in-place algorithm can cause side effects.
Your input is "destroyed" or "altered," which can affect
code outside of your function. For
example:
Generally, out-of-place algorithms are considered safer
because they avoid side effects. You should only use an
in-place algorithm if you're space constrained or
you're positive you don't need the original input
anymore, even for debugging.
Overview
def roll_die():
return random.randint(1, 6)
def roll_two_and_sum():
total = 0
total += roll_die()
total += roll_die()
print(total)
roll_two_and_sum()
roll_two_and_sum()
roll_die()
roll_two_and_sum()
random.randint()
roll_die()
roll_two_and_sum()
roll_die()
roll_two_and_sum()
roll_two_and_sum()
roll_die()
roll_two_and_sum()
random.randint()
roll_die()
roll_two_and_sum()
roll_two_and_sum()
print()()
roll_two_and_sum()
What's stored in a stack frame?
The Space Cost of Stack Frames
def product_1_to_n(n):
return 1 if n <= 1 else n * product_1_to_n(n - 1)
product_1_to_n() n = 10
product_1_to_n() n = 9
product_1_to_n() n = 10
product_1_to_n() n = 8
product_1_to_n() n = 9
product_1_to_n() n = 10
product_1_to_n() n = 1
product_1_to_n() n = 2
product_1_to_n() n = 3
product_1_to_n() n = 4
product_1_to_n() n = 5
product_1_to_n() n = 6
product_1_to_n() n = 7
product_1_to_n() n = 8
product_1_to_n() n = 9
product_1_to_n() n = 10
def product_1_to_n(n):
# We assume n >= 1
result = 1
for num in range(1, n + 1):
result *= num
return result
product_1_to_n() n = 10, result = 1, num = 1
product_1_to_n() n = 10, result = 2, num = 2
product_1_to_n() n = 10, result = 6, num = 3
product_1_to_n() n = 10, result = 24, num = 4
def square_list_in_place(int_list):
for index, element in enumerate(int_list):
int_list[index] *= element
# NOTE: no need to return anything - we modified
# int_list in place
def square_list_out_of_place(int_list):
# We allocate a new list with the length of the input list
squared_list = [None] * len(int_list)
for index, element in enumerate(int_list):
squared_list[index] = element ** 2
return squared_list
original_list = [2, 3, 4, 5]
square_list_in_place(original_list)
print("original list: %s" % original_list)
# Prints: original list: [4, 9, 16, 25], confusingly!
Why a list of characters instead of a string?
The goal of this
question is to practice manipulating strings
in place. Since we're modifying the
input, we need
a
mutable
↴
A mutable object can be changed after it's
created, and an immutable object can't.
For example, lists are mutable in Python:
And tuples are immutable:
Strings can be mutable or immutable depending
on the language.
Strings are immutable in Python:
But in some other languages, like Ruby, strings
are mutable:
Mutable objects are nice because you can make
changes in-place, without allocating a new
object. But be careful—whenever you make an in-place change
to an object, all references to that object will now
reflect the change.
int_list = [4, 9]
int_list[0] = 1
# int_list is now [1, 9]
int_tuple = (4, 9)
int_tuple[0] = 1
# Raises: TypeError: 'tuple' object does not support item assignment
test_string = 'mutable?'
test_string[7] = '!'
# Raises: TypeError: 'str' object does not support item assignment
test_string = 'mutable?'
test_string[7] = '!'
# test_string is now 'mutable!'
In general, an
in-place
↴
An in-place function
modifies data structures or objects outside of its
own
stack frame
↴
The call stack is what a program uses to keep
track of function calls. The call stack is
made up of stack frames—one for
each function call.
For instance, say we called a function that
rolled two dice and printed the sum.
First, our program calls roll_two_and_sum(). It goes
on the call stack:
That function calls roll_die(), which gets pushed
on to the top of the call stack:
Inside of roll_die(), we call random.randint().
Here's what our call stack looks like then:
When random.randint() finishes, we return back to
roll_die() by removing
("popping") random.randint()'s stack frame.
Same thing when roll_die() returns:
We're not done yet! roll_two_and_sum()
calls roll_die() again:
Which calls random.randint() again:
random.randint() returns, then roll_die() returns,
putting us back in roll_two_and_sum():
Which calls print()():
What actually goes in a function's
stack frame?
A stack frame usually stores:
Some of the specifics vary between processor architectures. For
instance, AMD64 (64-bit x86) processors pass some arguments in
registers and some on the call stack. And, ARM processors (common
in phones) store the return address in a special register instead
of putting it on the call stack.
Each function call creates its own stack
frame, taking up space on the call stack. That's important
because it can impact the space complexity of an algorithm.
Especially when we use recursion.
For example, if we wanted to multiply all the numbers
between 1 and n,
we could use this recursive approach:
What would the call stack look like
when n = 10?
First, product_1_to_n() gets called
with n = 10:
This calls product_1_to_n() with
n = 9.
Which calls product_1_to_n()
with n = 8.
And so on until we get to n = 1.
Look at the size of all those stack frames! The entire call stack
takes up O(n) space. That's right—we
have an O(n) space cost even though
our function itself doesn't create any data
structures!
What if we'd used an iterative approach instead of a recursive one?
This version takes a constant amount of space. At the beginning of the loop,
the call stack looks like this:
As we iterate through the loop, the local variables change, but we
stay in the same stack frame because we don't call any other
functions.
In general, even though the compiler or interpreter will take
care of managing the call stack for you, it's important to consider the
depth of the call stack when analyzing the space complexity of an
algorithm.
Be especially careful with recursive functions!
They can end up building huge call stacks.
What happens if we run out of space? It's a stack
overflow! In Python 3.6, you'll get
a RecursionError.
If the very last thing
a function does is call
another function, then its stack frame
might not be needed any more. The function
could free up its stack frame before doing its final
call, saving space.
This is called tail call optimization
(TCO). If a recursive function is optimized with TCO, then it
may not end up with a big call stack.
In general, most languages don't provide TCO. Scheme
is one of the few languages that guarantee tail call
optimization. Some Ruby, C, and Javascript
implementations may do it. Python and Java decidedly
don't.
In-place algorithms are sometimes called
destructive, since the original input is
"destroyed" (or modified) during
the function call.
Careful: "In-place" does not mean "without
creating any additional variables!" Rather, it means
"without creating a new copy of the input." In general, an
in-place function will only create
additional variables that are O(1) space.
An out-of-place function
doesn't make any changes that are visible to
other functions. Usually,
those functions copy any data structures or objects
before manipulating and changing them.
In many languages, primitive values (integers,
floating point numbers, or characters) are copied when passed as
arguments, and more complex data structures
(lists, heaps, or hash tables) are
passed by
reference. This is what Python does.
Here are two functions that do the same
operation on a list, except one is
in-place and the other is out-of-place:
Working in-place is a good way to save time and
space. An in-place algorithm avoids the cost of
initializing or copying data structures, and it usually has
an O(1) space cost.
But be careful: an in-place algorithm can cause side effects.
Your input is "destroyed" or "altered," which can affect
code outside of your function. For
example:
Generally, out-of-place algorithms are considered safer
because they avoid side effects. You should only use an
in-place algorithm if you're space constrained or
you're positive you don't need the original input
anymore, even for debugging.
Overview
def roll_die():
return random.randint(1, 6)
def roll_two_and_sum():
total = 0
total += roll_die()
total += roll_die()
print(total)
roll_two_and_sum()
roll_two_and_sum()
roll_die()
roll_two_and_sum()
random.randint()
roll_die()
roll_two_and_sum()
roll_die()
roll_two_and_sum()
roll_two_and_sum()
roll_die()
roll_two_and_sum()
random.randint()
roll_die()
roll_two_and_sum()
roll_two_and_sum()
print()()
roll_two_and_sum()
What's stored in a stack frame?
The Space Cost of Stack Frames
def product_1_to_n(n):
return 1 if n <= 1 else n * product_1_to_n(n - 1)
product_1_to_n() n = 10
product_1_to_n() n = 9
product_1_to_n() n = 10
product_1_to_n() n = 8
product_1_to_n() n = 9
product_1_to_n() n = 10
product_1_to_n() n = 1
product_1_to_n() n = 2
product_1_to_n() n = 3
product_1_to_n() n = 4
product_1_to_n() n = 5
product_1_to_n() n = 6
product_1_to_n() n = 7
product_1_to_n() n = 8
product_1_to_n() n = 9
product_1_to_n() n = 10
def product_1_to_n(n):
# We assume n >= 1
result = 1
for num in range(1, n + 1):
result *= num
return result
product_1_to_n() n = 10, result = 1, num = 1
product_1_to_n() n = 10, result = 2, num = 2
product_1_to_n() n = 10, result = 6, num = 3
product_1_to_n() n = 10, result = 24, num = 4
def square_list_in_place(int_list):
for index, element in enumerate(int_list):
int_list[index] *= element
# NOTE: no need to return anything - we modified
# int_list in place
def square_list_out_of_place(int_list):
# We allocate a new list with the length of the input list
squared_list = [None] * len(int_list)
for index, element in enumerate(int_list):
squared_list[index] = element ** 2
return squared_list
original_list = [2, 3, 4, 5]
square_list_in_place(original_list)
print("original list: %s" % original_list)
# Prints: original list: [4, 9, 16, 25], confusingly!
We swap the first and last characters, then the second and second-to-last characters, and so on until we reach the middle.
def reverse(list_of_chars):
left_index = 0
right_index = len(list_of_chars) - 1
while left_index < right_index:
# Swap characters
list_of_chars[left_index], list_of_chars[right_index] = \
list_of_chars[right_index], list_of_chars[left_index]
# Move towards middle
left_index += 1
right_index -= 1
O(n) time and O(1) space.
Do you have an answer?
Wanna review this one again later? Or do you feel like you got it all?
Mark as done Pin for review laterWant more coding interview help?
Check out interviewcake.com for more advice, guides, and practice questions.
Reset editor
Powered by qualified.io
With just a couple clicks.
We'll never post on your wall or message your friends.
Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?